Low-cost electronic microchips, for example of the RFID type, are used in many applications such as labeling or tracking objects (medication, library books, etc.) and producing and verifying electronic tickets, such as public transport tickets.
Regardless of the application concerned, it is necessary to prevent fraud by counterfeiting the microchips, in particular copying or cloning them or replaying the data that they transmit. To protect the applications against such attacks, it is imperative to authenticate microchips when they interact with a microchip reader.
However, any authentication protocol used between an entity to be authenticated, such as a low-cost microchip, and the verification entity, such as a microchip reader, must take into account the extremely limited computation resources of microchips of this type, which are usually of the hard-wired logic type.
The symmetrical HB+ (Hopper-Blum) authentication protocol specifically designed to meet the requirements of RFID microchips has recently been proposed (see A. Juels and S. A. Weis, “Authenticating Pervasive Devices with Human Protocols”, in V. Shoup, Editor, Advances in Cryptology-Crypto 05, Lecture Notes in Computer Science, Vol. 3126, pp. 293-308, Springer Verlag).
FIG. 1 represents exchange of data under the HB+ protocol between the entity to be authenticated and the verification entity.
As can be seen in this figure, the entity to be authenticated, for example an RFID microchip, and the verification entity, for example a microchip reader, share a pair of secret keys x and y consisting of binary vectors of n bits. These secret keys are stored in storage means 10 of the microchip and storage means 20 of the microchip reader.
The HB+ protocol unfolds over r successive iterations. On each iteration, the microchip draws at random (block 100) and sends (1) the microchip reader a binary vector b of n bits. Similarly, the microchip reader draws at random (block 200) and sends (2) the microchip a binary vector a of n bits. The random drawing of the vectors b and a is effected in accordance with a uniform probability law.
The microchip then responds to the challenge a launched by the microchip reader by calculating (block 120) and sending it (3) a response affected by noise z=a•x⊕b•y⊕ν, where • represents the modulo 2 scalar product operation and ⊕ represents modulo 2 addition. A noise bit ν is drawn at random by the microchip (block 110); it takes the value 1 with a probability η<½ and the value 0 with a probability (1−η).
The microchip reader rejects the current iteration (block 210) if the response z received does not satisfy the equation z=a•x⊕b•y; in this situation, a counter of the number nbr of rejected iterations is incremented by one unit (block 220). At the end of the r iterations, counted by a counter of the number nbt of iterations (block 250), the authentication is accepted (block 240) if and only if the number nbr of rejected iterations from the counter is below a given threshold t (block 230). The value of t is of course a function of the probability η; a simple value of t is for example t=r×η.
Although the exchanges of the proposed HB+ protocol are structured in r iterations of three passes, it is possible to reduce this to one exchange of three passes by calculating and sending r values of b, a, and z at the same time.
The advantage of the HB+ protocol is the great simplicity of the authentication calculations.
Moreover, its robustness stems from the difficulty of the LPN (Learning Parity with Noise) problem of finding a solution to a linear system with noise. Finally, compared to the historically earlier HB protocol that differs from it in that the response with noise comprises no term b•y, the HB+ protocol has the benefit that the masking effect induced by the binary vector b is coupled to the secret key y; the HB protocol was sensitive to attacks in which the adversary sends constant challenges a and listens to the responses from the microchip reader; the most frequent response being a•x, and a being known, it was possible in a first step to obtain a•x for a sufficient number of values of a and in a second step to deduce x by solving a linear system.
However, the HB+ protocol has drawbacks that prevent it from being used effectively in practice.
As already indicated, a first drawback is that although this protocol is resistant to some active attacks on a, it nevertheless remains vulnerable to other attacks encountered when an adversary has access to the result (success/failure) of a plurality of successive authentications.
Such an attack intercepts the challenge a when sent from the microchip reader to the microchip and modifies its bits successively. For example, if the first bit of a is modified, it is clear that if the result is not changed after this modification it can be concluded that the first bit of the secret vector x is likely to be 0. Conversely, if the result is changed, the first bit of x is probably equal to 1. To obtain all of the n bits of x, it suffices to modify the second bit of a to discover the second bit of x, and so on up to bit n.
A second drawback of the HB+ protocol is that it produces an excessive number of false alarms, a false alarm being defined as refusal to authenticate a legitimate microchip. With the following values: n=224 bits, η=0.25, r=100 iterations and t=η×r=25, for example, the false alarm rate is 45%, which is totally unacceptable. The false positives rate, i.e. successful authentication of chips responding at random, is close to 3×10−7.
If instead of taking for t the expected value t=η×r=25, a higher value is taken, for example 35, the false alarm rate falls to 1%, which remains unacceptable, but the false positive rate increases to approximately 1.7×10−3.
Finally, a third drawback of HB+ is the excessive complexity to which it leads in communication between the microchip and the microchip reader. With the same numerical values as before, it can be shown that is necessary to exchange 44 900 bits on each authentication, i.e. 224 bits for b, 224 bits a, and one bit for the result z in each of the 100 iterations.
Even with a bit rate of 10 000 bps, the microchip reader requires more than four seconds to authenticate a microchip, which is prohibitive in terms of system ergonomics, not to mention the resulting problem of supplying power to the microchip.